HW#4 --- last modified March 02 2019 21:31:28..

Solution set.

Due date: Nov 13

Files to be submitted:
  Hw4.zip

Purpose: To gain experience showing problems are NP-complete. To learn a little about the classes coNP, RP, BPP, PP.

Related Course Outcomes:

Problems 1 and 2 are related to the course outcome (3) [Show the completeness of a complete problem for each of these classes] --in this case for the classes NP and coNP.

Problems 3 and 4 are related to the course outcome (4) [Know properties of the randomized classes RP, BPP]. The coding problem also gives you some experience with randomized algorithms for languages in these classes.

Specification:

First, write up the following problems in Hw4.tex:

1. A database table T is a collection of rows, each row consisting of columns of values from some finite set D. Given a set of tables T₁, … T_n, a conjunctive query is a query of the form

∃ y₁ ∃ y₂ .. ∃ y_v [A₁ ∧ … ∧ A_m]

Here each A_i is of the form (u₁,…u_k) ∈ T where T is one of the tables (you can use the same table more than once), and each u_j is either an element of the domain D, one of y₁, …y_v, or a free variable x₁, …x_t. The query returns rows as a results rows (x₁, ..., x_s) such that we can find y_i's such that the query predicate holds.

As an example, suppose we had two tables Employee(Name, Age, Salary) and Works_On(Name, Project). Employee might have rows:

(Bob, 27, 55k)
(Veronica, 87, 25k)
(John, 16, 18k)

Works_On might have rows:

(Bob, StarBurst)
(Veronica, Oak)
(John, SaltRecovery)

A query might be:

∃ y Employee(x, y, 55k) ∧ Works_On(x, StarBurst)

This query returns one row:

(Bob)

Consider the problem given a query Q over a set of tables T₁, …, T_n whose column values come from a set D, does Q return any rows? Show this problem is NP-complete.

2. Consider the problem: Given a formula F, is the variable x set to true in all satisfying assignments of F? Show this problem is coNP-complete.

3. Show that the class PP is closed under complements of languages.

4. Show RP and BPP are closed under logspace reductions. Why can't we do a straightforward variant of of the halting problem as in HW3 to find complete problems for these classes?

For the coding part of the assignment I want you to implement the random walk algorithm for 2SAT given on pages 245-246 out of the book. Your program will be run from the command line with a line like:

java RandomWalk instance.txt

Here the file instance.txt contains an instance of 2SAT (or 3SAT) encoded using the same encoding as for 3SAT on HW3. Have fun experimenting with the algorithm as well on 3SAT instances to see which ones it performs well on and which it performs poorly on. Write a paragraph commentary in your comments summarizing your findings.

Point Breakdown